package LearnAlgorithm.j_动态规划and贪心算法;

import java.util.Arrays;
import java.util.Scanner;

/*
原始问题：
一个线段上有很多个区间，有不重叠的，重叠的，重合的...
线段上任取一点，这个点在某线段A内，那么A就被命中
求命中所有线段的最少的点的数量
 */
public class c区间选点by贪心 {
	public static void main(String[] args) {
		/*
		in 7 
		1 2 3 5 8 10 11
		3 5 6 7 9 12 12
		out 4
		 */
		c区间选点by贪心 test = new c区间选点by贪心();
		test.useGreedyAlgorithm2();
	}
	
	public void useGreedyAlgorithm2() {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int[] start = new int[n];
		int[] terminate = new int[n];
		Segment[] segments = new Segment[n];
		for (int i = 0; i < n; i++) {
			start[i] = scanner.nextInt();
		}
		for (int i = 0; i < n; i++) {
			terminate[i] = scanner.nextInt();
		}
		for (int i = 0; i < n; i++) {
			segments[i] = new Segment(start[i], terminate[i]);
		}
		Arrays.sort(segments);
		int res = GreedyAlgorithm2(segments, n);
		System.out.println(res);
	}
	
	public int GreedyAlgorithm2(Segment[] segments, int n) {
		int count = 1;
		int current = segments[0].terminate;
		for (int i = 1; i < n; i++) {
			if (current < segments[i].terminate && segments[i].start > current) {
				count++;
				current = segments[i].terminate;
			}
		}
		return count;
	}
	
	private static class Segment implements Comparable<Segment> {
		int start;
		int terminate;
		public Segment(int start, int terminate) {
			this.start = start;
			this.terminate = terminate;
		}
		@Override
		/**
			this是新元素，other是老元素
			this.string.compareTo(other.string)会返回一个int A
			Suff类的compareTo会返回一个int,实际上就是把A返回
			在使用了自然排序的集合中添加Suff类对象
			这些对象的顺序是根据A决定的
			A = 0，在有些集合中，新元素(this)就不会加入；Array.sort不会导致“不加入”
			A > 0，this在other后面加入
			A < 0，this在other前面加入
		 */
		public int compareTo(Segment o) {
			int x = this.terminate - o.terminate;
			if (x == 0) {
				return this.start - o.start;//本题也一样。t相同情况下，线段长短不同：短的排在前 与 长的排在前 这两种处理方法，没区别
				//所以这里谁减谁都可以
			}
			return x;
		}
	}
}
